package com.mdnote.structure.treeapplication;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/4
 * @description AVL树
 */
public class AvlTree {

    private static class Node {

        private int value;
        private Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }

        private void add(Node node) {
            if (node == null) {
                return;
            }
            if (node.value <= this.value) {
                if (this.left != null) {
                    this.left.add(node);
                } else {
                    this.left = node;
                }
            } else {
                if (this.right != null) {
                    this.right.add(node);
                } else {
                    this.right = node;
                }
            }

            // 添加完检查一下是否平衡
            if (this.leftLength() - this.rightLength() > 1) {

                // 看看需不需要左旋
                if (this.left != null && this.left.rightLength() > this.left.leftLength()) {
                    this.left.leftRotate();
                }
                // 右旋
                rightRotate();
//                return;
            }
            // 右子树比较高，需要左旋
            if (this.rightLength() - this.leftLength() > 1) {

                // 看看需不需要
                if (this.right != null && this.right.leftLength() > this.right.rightLength()) {
                    this.right.rightRotate();
                }
                // 左旋
                leftRotate();
            }
        }

        private void infixOrder() {
            if (this.left != null) {
                this.left.infixOrder();
            }
            System.out.print(this.value + " ");
            if (this.right != null) {
                this.right.infixOrder();
            }
        }

        /**
         * 找到某个节点
         * @param value 节点的值
         * @return 节点
         */
        private Node search(int value) {
            if (this.value == value) {
                return this;
            }
            Node temp = null;
            if (this.left != null && value <= this.value) {
                temp = this.left.search(value);
            }
            if (temp == null) {
                if (this.right != null && value > this.value) {
                    return this.right.search(value);
                }
            }
            return temp;
        }

        /**
         * 查询某个节点的父节点
         * @param value 节点
         * @return 该节点的父节点
         */
        public Node searchParent(int value) {
            if (this.left != null && this.left.value == value) {
                return this;
            }
            if (this.right != null && this.right.value == value) {
                return this;
            }
            Node temp = null;
            if (this.left != null && value <= this.value) {
                temp = this.left.searchParent(value);
            }
            if (temp == null && this.right != null && value > this.value) {
                temp = this.right.searchParent(value);
            }
            return temp;
        }

        /**
         * 返回深度
         * @return 深度
         */
        private int length() {
            return Math.max(this.left != null ? this.left.length() : 0, this.right != null ? this.right.length() : 0) + 1;
        }

        /**
         * 返回左子树最大深度
         * @return 深度
         */
        private int leftLength() {
            return this.left == null ? 0 : this.left.length();
        }


        /**
         * 返回右子树最大深度
         * @return 深度
         */
        private int rightLength() {
            return this.right == null ? 0 : this.right.length();
        }

        /**
         * 左旋
         */
        private void leftRotate() {
            // 由于右子树过高才需要左旋
            // 创建新节点
            Node newNode = new Node(this.value);
            // 让新节点的左指针指向当前节点的左节点
            newNode.left = this.left;
            // 让新节点的右指针指向当前节点的右节点的左节点
            newNode.right = this.right.left;
            // 将当前节点的值改成右节点的值
            this.left = newNode;
            // 当前节点的左指针指向新节点
            this.value = this.right.value;
            // 当前节点的右指针指向右节点的右节点
            this.right = this.right.right;
        }

        /**
         * 右旋
         */
        private void rightRotate() {
            // 是因为左边子树太高才要右旋
            Node newNode = new Node(this.value);
            newNode.left = this.left.right;
            newNode.right = this.right;
            this.value = this.left.value;
            this.left = this.left.left;
            this.right = newNode;
        }
    }

    private Node root;

    /**
     * 添加节点
     * @param node 待添加的节点
     */
    public void add(Node node) {
        if (root == null) {
            root = node;
            return;
        }
        root.add(node);


    }

    /**
     * 中序遍历  升序
     */
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        }
    }

    /**
     * 查找某个节点
     * @param value 节点的值
     * @return 节点
     */
    public Node search(int value) {
        if (root == null) {
            return null;
        }
        return root.search(value);
    }

    /**
     * 查询目标的父节点
     * @param value 节点的值
     * @return 父节点
     */
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        }
        if (root.value == value) {
            return null;
        }
        return root.searchParent(value);
    }

    /**
     * 删除某个几点
     * @param value 节点的值
     */
    public void remove(int value) {
        // 删除分三种情况 1.叶子节点 2.左或者右有子树 3. 左右都有子树
        Node targetNode = search(value);
        if (targetNode == null) {
            return;
        }
        Node parentNode = searchParent(value);
        // 1. 叶子节点
        if (targetNode.left == null && targetNode.right == null) {
            // 如果只有根节点，直接删除
            if (targetNode == root) {
                root = null;
                return;
            }
            // 看一下目标节点是父节点的左还是右
            if (parentNode != null && parentNode.left != null && parentNode.left.value == targetNode.value) {
                parentNode.left = null;
            }
            if (parentNode != null && parentNode.right != null && parentNode.right.value == targetNode.value) {
                parentNode.right = null;
            }
        } else if (targetNode.left != null && targetNode.right != null) {
            // 3. 删除的节点有左右字数
            // 找到左子树的最大值并把它删除
            int maxValue = getAndRemoveMax(targetNode.left);
            // 把最小值放到value中
            targetNode.value = maxValue;
        } else  {
            // 2. 删除的节点有左子树
            if (parentNode != null && parentNode.left != null && parentNode.left.value == targetNode.value) {
                if (targetNode.left != null) {
                    parentNode.left = targetNode.left;
                } else {
                    parentNode.left = targetNode.right;
                }
            }
            if (parentNode != null && parentNode.right != null && parentNode.right.value == targetNode.value) {
                if (targetNode.left != null) {
                    parentNode.left = targetNode.left;
                } else {
                    parentNode.left = targetNode.right;
                }
            }
            // 删除根节点时 根节点左边或者右边只有一棵树，这时候我们只需要让子树节点成为根节点就可以了
            if (parentNode == null) {
                if (targetNode.left != null) {
                    root = targetNode.left;
                }
                if (targetNode.right != null) {
                    root = targetNode.right;
                }
            }
        }
    }

    /**
     * 获取子树最大值并删除节点
     * @param node 根节点
     * @return 子树最大值
     */
    private int getAndRemoveMax(Node node) {
        Node temp = node;
        int maxValue = Integer.MIN_VALUE;
        Node removeNode = null;
        while (temp != null) {
            if (temp.value > maxValue) {
                maxValue = temp.value;
                removeNode = temp;
            }
            temp = temp.right;
        }
        if (removeNode != null) {
            remove(removeNode.value);
        }
        return maxValue;
    }


    public static void main(String[] args) {
        AvlTree binarySearchTree = new AvlTree();
//        int[] arr = {7, 3, 10, 1, 5, 8, 12, 2};
        int[] arr = {10, 11,7, 6, 9, 8};
        for (int i : arr) {
            binarySearchTree.add(new Node(i));
        }

        binarySearchTree.infixOrder();
        System.out.println();
        System.out.println("左边的高度：" +binarySearchTree.root.leftLength());
        System.out.println("右边的高度：" +binarySearchTree.root.rightLength());


//        binarySearchTree.remove(1);
//        binarySearchTree.remove(2);
//        binarySearchTree.remove(5);
//        binarySearchTree.remove(8);
//        binarySearchTree.remove(12);
//        binarySearchTree.infixOrder();
//        System.out.println();
//        binarySearchTree.remove(3);
//        binarySearchTree.remove(7);
//        binarySearchTree.remove(10);
//        binarySearchTree.infixOrder();

    }
}
